package two.chapter_2.c2_2;

import two.chapter_2.c2_1.Sortable;

/**
 * 自顶向下的归并排序
 * 分治思想
 * 将一个数组分成两个子数组，分别进行排序，这两部分排序完成后，再归并成一个数组
 * @param <Item>
 */
public class MergeSort<Item extends Comparable<Item>> extends Sortable<Item> {


    private Object[] aux;//辅助数组
   // private Item[] aux; 编译期泛型类型擦除，在运行阶段其他是Object类型数组
    @Override
    public void sort(Item[] items) {
        aux=new Object[items.length];
        sort(items,0,items.length-1);
    }

    /**
     * 增加数量级   比较次数
     *             最坏情况：C(N)<=C(N/2)+C(N/2)+N;
     *             C(N/2)为左半边数组排序需要的比较次数
     *             C(N/2)为右半边数组排序需要的比较次数
     *             N为归并左右两部分所需的做多的比较次数
     *
     *             最好情况
     *             归并左右两部分所需的做少的比较次数N/2
     *             即：C(N)>=C(N/2)+C(N/2)+N/2;
     *
     *             当N=2^h时，即完全二叉树结点总数，且等号成立时
     *
     *             C(2^h)=2C(2^(h-1))+2^h
     *             两边同时除以2^h
     *              C(2^h)/2^h =C(2^(h-1))/2^(h-1)+1
     *              用这个公式替换右边第一项
     *               C(2^h)/2^h =C(2^(h-2))/2^(h-2)+1+1
     *               重复n-1遍
     *                  C(2^h)/2^h =C(2^0)/2^0+h
     *                两边同时乘以2^h
     *                C(2^h)=h*2^h;
     *                C(N)=NlogN
     * 结论：对于长度为N的任意数组，自顶向下的归并排序需要1/2NlogN至NlogN次比较
     *
     * @param items
     * @param lo
     * @param hi
     */
    private void sort(Item[] items,int lo,int hi){
        if (lo>=hi){
            return;
        }
        int mid=lo+(hi-lo)/2;
        sort(items,lo,mid);
        sort(items,mid+1,hi);
        merge(items,lo,mid,hi);
    }

    private void merge(Item[] items, int lo, int mid, int hi) {
        //将items[lo...mid] 和 items[mid+1,hi]两部分归并
        //将数据保存到辅助数组
        for (int i=lo;i<=hi;i++){
            aux[i]=items[i];
        }
        /*      i          j
                ---------- --------
                lo       mid+1     hi
         */
        int i=lo;
        int j=mid+1;

        //items[i]<items[j]
        for (int k=lo;k<=hi;k++) {
            if (i >= mid + 1) {  //i指针走完
                items[k]= (Item) aux[j++];
            }else if (j>hi){ //j指针走完
                items[k]= (Item) aux[i++];
            }else if (less((Item)aux[i],(Item)aux[j])){
                items[k]= (Item) aux[i++];
            }else {
                items[k]= (Item) aux[j++];
            }
        }


    }
}
